package com.yeung.dynamicplan;

public class 动态规划背包问题 {
    public static void main(String[] args) {
        int[] w = {0, 2, 3, 4, 5, 9};
        int[] v = {0, 3, 4, 5, 8, 10};

    /*    int[] w = {0, 4, 6, 2, 2, 5, 1};
        int[] v = {0, 8, 10, 6, 3, 7, 2};*/
        int W = 12;
        int[][] b = getLargestValue(w, v, W);
        System.out.println(b[w.length - 1][b[0].length - 1]);
        //使用递归的方法
        int value = getValue(w, v, W, 0);
        System.out.println(value);
    }

    /**
     * 优化版动态规划
     *
     * @param w
     * @param v
     * @param W
     * @return
     */
    private static int[][] getLargestValue(int[] w, int[] v, int W) {

        int N = w.length;//确定物品的数量和背包的限重
        int[][] b = new int[N][W + 1];
        //开始动态规划
        for (int k = 1; k < N; k++) {
            for (int c = 1; c <= W; c++) {//假设容量从1到限定的21, 之间的情况
                if (w[k] > c) {//要拿的物品大于背包剩余容量
                    b[k][c] = b[k - 1][c];
                } else {
                    int value1 = b[k - 1][c - w[k]] + v[k]; // 拿第k件物品
                    int value2 = b[k - 1][c]; // 不拿第k件物品
                    b[k][c] = Math.max(value1, value2);
                }
            }
        }
        for (int[] ints : b) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
        return b;
    }

    /**
     * @param w        重量数组
     * @param v        物品价值数组
     * @param capacity 背包容量
     * @param i        物品i开始 0
     * @return
     */
    private static int getValue(int[] w, int[] v, int capacity, int i) {
        if (i == w.length - 1) {
            //最后一件物品
            return w[i] <= capacity ? v[i] : 0;
        } else {
            if (capacity < w[i]) {
                //背包装不了不了的情况
                return getValue(w, v, capacity, i + 1);
            }
            //能装下, 但是考虑拿不拿
            //拿
            int v1 = getValue(w, v, capacity - w[i], i + 1) + v[i];
            //不拿
            int v2 = getValue(w, v, capacity, i + 1);
            return Math.max(v1, v2);
        }
    }
}
